觀前提醒：

1. 我預設大家已經先思考並分析過題目，沒啥想法才開始 google 找解題靈感。若無，建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法。
2. 承上，既然已經有思考過了，那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了，那我可能解題想法 & 心得的部分就不會寫太多，免得干擾你的思考。
3. 所有解法都是已經取得系統的 Accepted，但或許不是最優解法，請多包涵。
4. 若對於解法不太懂，可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
5. 最後，歡迎在下面留言指教~教學相長才會進步歐~

題目

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

解題想法

簡單說，我是利用 Stack 的概念，來處理這題的。關於 Stack，詳情請參考下方連結~
Stack: Intro(簡介)

上面文章，開宗明義就提到以下訊息：

Stack 是具有「 Last-In-First-Out 」的資料結構(可以想像成一種裝資料的容器)，「最晚進入 Stack 」的資料會「 最先被取出 」，「 最早進入 Stack 」的資料則「最晚被取出」。

再搭配 LeetCode 提供的 GIF，給大家 30 秒的時間思考一下~

沒錯~我們的做法，掌握住 Stack 後，處理方式就變得相當簡單：

1. 先宣告一個空陣列，當作是 Stack。
2. 把括號分為左右兩組，遇到左括號就直接通通 push 進 Stack 中。
3. 若遇到右括號，利用 if-else 的方式，檢視其性質(大 or 中 or 小)；再檢視 Stack最上方(最末位)，是否為其相對應的左括號。若是，則把該 Stack 中的左括號消去。
4. 若不符合以上情況，則 return false。(eq: “]”，只有右邊括號，沒有左邊括號的情況)
5. 跑完整個字串 s 後，若 Stack 的長度為"0"，就代表合法，反之則不合法。

有了想法後，接下來我們來時做看看 CODE 吧~

CODE

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  if (s === null || s.length <= 0) return true;
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(" || s[i] === "{" || s[i] === "[") {
      stack.push(s[i]);
    } else if (s[i] === ")" && stack[stack.length - 1] === "(") {
      stack.pop();
    } else if (s[i] === "}" && stack[stack.length - 1] === "{") {
      stack.pop();
    } else if (s[i] === "]" && stack[stack.length - 1] === "[") {
      stack.pop();
    }
    // 若不符合以上情況，則 return false。(eq: "]"，只有右邊括號，沒有左邊括號的情況)
    else return false;
  }
  return stack.length === 0;
};

心得

在實作中，我還使用了 .pop() 的技巧，以下提供 MDN 的連結，供大家參考~
Array.prototype.pop()

謝謝大家的收看，LeetCode 小學堂我們下次見~